﻿#define _CRT_SECURE_NO_WARNINGS 1
//题目：最长上升子序列I
//给定一个长度为 N的数列，求数值严格单调递增的子序列的长度最长是多少。
//输入格式
//第一行包含整数 N。
//第二行包含 N个整数，表示完整序列。
//输出格式
//输出一个整数，表示最大长度。
//数据范围
//1≤N≤1000，−109≤数列中的数≤109
//输入样例：
//7
//3 1 2 1 8 5 6
//输出样例：
//4

//f[i] = max(f[i],f[j] + 1) ,动态规划公式
//#include<iostream>
//#include<algorithm>
//using namespace std;
//const int N = 1010;
//int a[N], dp[N];
//int n;
//
//int main()
//{
//    cin >> n;
//    for (int i = 1; i <= n; i++) cin >> a[i];
//    for (int i = 1; i <= n; i++)
//    {
//        dp[i] = 1;
//        for (int j = 1; j < i; j++)
//        {
//            if (a[j] < a[i])
//                dp[i] = max(dp[i], dp[j] + 1);
//        }
//    }
//    int res = dp[1];
//    for (int i = 1; i <= n; i++) res = max(dp[i], res);
//    cout << res << endl;
//    return 0;
//}


//保存最长上升子序列
//#include<iostream>
//#include<algorithm>
//using namespace std;
//const int N = 1010;
//int a[N], dp[N], Prev[N];
//int n;
//int main()
//{
//    cin >> n;
//    for (int i = 1; i <= n; i++) cin >> a[i];
//    for (int i = 1; i <= n; i++)
//    {
//        dp[i] = 1;//每个数开始只有一个子序列
//        Prev[i] = 0;//先让每一个的前面都为0
//        for (int j = 1; j < i; j++)
//        {
//            if (a[j] < a[i])
//            {
//                if (dp[i] < dp[j] + 1)
//                {
//                    dp[i] = dp[j] + 1;
//                    Prev[i] = j;//记录上升子序列的下标
//                }
//            }
//        }
//    }
//    int k = 1;
//
//    for (int i = 1; i <= n; i++)
//    {
//        if (dp[k] < dp[i])
//        {
//            k = i;
//        }
//    }
//    cout << dp[k] << endl;
//    for (int i = 1, len = dp[k]; i <= len; i++)
//    {
//        cout << a[k] << ' ';
//        k = Prev[k];
//    }
//    return 0;
//}